package PersonStu.siqi;

/**
 * @Author by KoVaVo
 * @Date 2023-01-04 21:23
 * @Desc:
 * 两个有序数组中第K小的数
 * 给定两个数组A和B
 * A是数组长度为m，元素从小到大是已经排好序的
 * B是数组长度为n，元素从小到大是已经排好序的
 * 找出这两个数组中第K大的数字返回
 * 要求时间复杂度为O(log{min{N,M}})
 * Math.min( logN,logM )
 * 思路：
 * 主要思路是找上中位数，使用上中位数作比较
 * 1、找到数组A的上中位数mid1，和数组B的上中位数mid2
 * 1、使用mid1和mid2作比较，
 * 1、如果两个数组的长度都是偶数
 * 如果mid1==mid2，那么上中位数就是mid1、mid2
 * 如果mid1 > mid2 ，那么在将s1...mid1和mid2...e2找
 * 1、如果两个数组的长度都是奇数
 */
public class code01_FindKthMinNumber {

    public static int findKthNum(int [] arrA,int [] arrB,int Kth){
        if(arrA == null || arrB == null){
            return -1;
        }
        int M = arrA.length;
        int N = arrB.length;

        if(Kth < 1 || Kth > M + N){
            return  -1;
        }
        //有可能A数组和B数组的长度不一致，那么找到长短数组
        int [] longs = M >= N ? arrA : arrB;
        int [] shorts = M < N ? arrA : arrB;
        int l = longs.length;
        int s = shorts.length;
        //如果要找的第K小的 K <= s
        if(Kth <= s){
            //那么第K小的数组可以浓缩两个数组
            // longs: 1 2 3 4 5
            //shorts: 1 2 3 4
            // 那么浓缩的范围如下
            return getUpMedia(shorts,0,Kth - 1,longs,0,Kth - 1);
        }
        //如果要找到的第K小的 K > l
        if(Kth > l){
            if(shorts[Kth-l-1] >= longs[l-1]){
                return shorts[Kth-l-1];
            }
            if(longs[Kth-s-1] >= shorts[s-1]){
                return longs[Kth-s-1];
            }
            return getUpMedia(shorts,Kth-l,s-1,longs,Kth-s,l-1);
        }
        //如果要找的第K小的 s < k <= l
        if(longs[Kth-s-1] >= shorts[s-1]){
            return longs[Kth-s-1];
        }
        return getUpMedia(shorts,0,s-1,longs,Kth-s,Kth-1);
    }

    /**
     *  A[s1...e1]
     *  B[s2...e2]
     *  A\B这两段一定等长且都有序
     *  求这两段整体上的中位数，上中位数值返回
     * @param A
     * @param s1
     * @param e1
     * @param B
     * @param s2
     * @param e2
     * @return 上中位数
     */
    private static int getUpMedia(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        int mid1 = 0;
        int mid2 = 0;
        while (s1 < e1){
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            if(A[mid1] == B[mid2]){
                //如果两个中位数相等，返回哪一个都行
                return A[mid1];
            }
            //如果数组的长度是奇数
            if(((e1-s1+1)&1)==1){
                if(A[mid1] > B[mid2]){
                    if(B[mid2] >= A[mid1-1]){
                        return B[mid2];
                    }
                    e1 = mid1 - 1;
                    s2 = mid2 + 1;
                }else{
                    //A[mid1]<B[mid2]
                    if(A[mid1] >= B[mid2]){
                        return A[mid1];
                    }
                    e2 = mid2 - 1;
                    s1= mid1 + 1;
                }
            }else{
                //偶数长度
                if(A[mid1] > B[mid2]){
                    e1 = mid1;
                    s2 = mid2 + 1;
                }else{
                    e2 = mid2;
                    s1 = mid1 +1;
                }
            }
        }
        return Math.min(A[s1],B[s2]);
    }

    public static void main(String[] args) {
        int[] A = {1,4,6,7,54,89};
        int[] B = {5,25,34,45};
        int Kth = 5;
        int kthNum = findKthNum(A, B, Kth);
        System.out.println(kthNum);
    }
}
